Interleaving Strings

Statement#

Given strings s1, s2, and s3, find whether an interleaving of s1 and s2 forms s3.

An interleaving of two strings a and b is a configuration where a and b splits into $n$ and $m$ substrings, respectively, such that:

• a $= a_{1}$ + $a_{2}$ + … + $a_{n}$
• b $= b_{1}$ + $b_{2}$ + … + $b_{m}$
• $\left | n - m \right | \leqslant 1$
• The interleaving can follow either of the following two formats:
  • $a_{1} + b_{1} + a_{2} + b_{2} + a_{3} + b_{3} + ...$
  • $b_{1} + a_{1} + b_{2} + a_{2} + b_{3} + a_{3} + ...$
• $a_{x}$ can be a consecutive sequence of characters in string s1.
• $b_{x}$ can be a consecutive sequence of characters in string s2.

Note: $a + b$ is the concatenation of the strings $a$ and $b$.

Let’s say we have two strings, “abc” and “xyz”. We may interleave them in multiple ways. We may alternately pick one character from each string until we have used up all the characters, giving us “axbycz” and “xaybzc”. Or, we may try to pick two characters at a time from each string, giving us “abxycz” and “xyabzc”. If we pick three characters at a time, we get “abcxyz” and “xyzabc”. Another class of variations is to pick a variable number of characters from each string, which leads to many more possibilities, such as “abxcyz”, “xayzbc”, and so on. However, “bxaycz” is not a valid interleaving, as the order of the characters taken from the first string is not preserved, since “b” appears here before “a”. Similarly, “acxybz” is not a valid interleaving.

Constraints:

• $0 \leq$ s1.length, s2.length $\leq 375$
• $0 \leq$ s3.length $\leq 750$
• s1, s2, and s3 consist of lowercase English letters.

Examples#

Try it yourself#

Implement your solution in the following playground:

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach#

A naive approach to deduce if s3 is indeed a result of interleaving s1 and s2 is to try and match the two strings with s3 one letter at a time. As an example, suppose we have the following strings:

• s1 = “abc”
• s2 = “xyz”
• s3 = “abxycz”

The first step is to verify if the length of s3 is equal to the sum of the lengths of s1 and s2. If it isn’t, return FALSE as the output. However, that isn’t the case for the given inputs. Therefore, we can traverse these strings and engage in the matching process. While traversing, we keep track of the indexes we are at in all three strings, allowing us to check the order in which these characters appear. Let’s see how it will work in this example with the help of the illustration below:

As we can see, we have two options at any step:

• If the letter at s1 index matches with the letter at s3 index, we consume both, that is, we move s1 index as well as s3 index one step forward. The matching process continues recursively for the portions of s1, s2, and s3 that we have not yet considered.
• If the letter at s2 index matches with the letter at s3 index, we consume both, that is, we move s2 index as well as s3 index one step forward. The matching process continues recursively for the portions of s1, s2, and s3 that we have not yet considered.

This process allows us to check all possible combinations of interleaving.

Let’s implement this naive approach:

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the above algorithm is $O(2^{s+t})$, where s and t are the lengths of s1 and s2, respectively.

Space complexity#

The space complexity of this naive approach is $O(s + t)$, where $s$ and $t$ are the lengths of s1 and s2, respectively. The solution uses the stack to store the data for each recursive call, and there may be at most $s + t$ calls in any given branch of the recursive call tree.

Optimized solution using dynamic programming#

As the naive approach is costly in terms of time complexity, we can try to optimize the solution using dynamic programming. Let’s see if this problem satisfies both conditions of dynamic programming:

• Optimal substructure: When we are presented with the problem of checking whether two strings, s1 and s2 have been interleaved to create s3, we compare the first character of s1 with the first character of s3, and if they match, we check the remaining characters of s1, the original characters of s2, and the remaining characters of s3. Denoting the length of s1 by $n_1$, the length of s2 by $n_2$ and the length of s3 by $n_3$, we can see that solving the problem for $\{n_1, n_2, n_3\}$ involves solving the smaller problem, $\{n_1-1, n_2, n_3-1\}$. In case it’s the first character of s2 that matches the first character of s3, we consume these matching characters and check the original characters of s1, the remaining characters of s2 and the remaining characters of s3. That is, we now need to solve the smaller problem represented by $\{n_1, n_2-1, n_3-1\}$. As solving a smaller version of the overall problem helps to solve it, this problem has the optimal substructure property.

• Overlapping subproblems: The following illustration highlights the overlapping subproblems. There are two recursive calls for s1 = “b”, s2 = “b”, s3 = “bb” (highlighted in peach), four calls for s1 = “”, s2 = “”, s3 = “” (highlighted in green), and so on. The function is computing certain results over and over again, which is inefficient. Therefore, this problem has the overlapping subproblems property.

Top-down solution#

The top-down solution improves on the recursive solution. Instead of repeatedly solving the same problems, we store the result of each subproblem and reuse it when needed. Let’s look at an example that would demonstrate this phenomenon:

• s1 = “ab”
• s2 = “ab”
• s3 = “aabb”

As illustrated above, the recursive solution involves solving several overlapping subproblems. However, it can be optimized with the help of memoization. In the recursive function, the indexes of s1, s2, and s3 uniquely identify each subproblem. So, we can store these subproblems in a hash table indexed by s1, s2, and s3 and look them up when required.

Let’s implement this memoization approach:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this approach is $O\left ( s \times t \right )$ where $s$ and $t$ are the lengths of s1 and s2, respectively.

Space complexity#

The space complexity would be $O\left ( s \times t \right )$ as we use a hash table of size $s \times t$ to store the subproblems we solve.

Bottom-up solution#

The first step of our bottom-up solution is to check if the lengths of s1 and s2 add up to the length of s3. If this is not the case, then s3 cannot be an interleaving of s1 and s2, so we can return FALSE without proceeding further.

If we pass the initial test then we can move on to constructing our solution. The bottom-up solution starts with the initialization of our lookup table. The lookup_table is created with an extra row and column to separate the base cases from the rest of the subproblems that we will solve later. The base cases for the problem are as follows:

• The top-left cell (s1_index = 0 and s2_index = 0) represents the case where the interleaved string s3 is empty. This cell will be TRUE if both s1 and s2 are empty.

• For the first column (s1_index > 0 and s2_index = 0), each cell will be filled with TRUE as long as the prefix of s3 up to that point is equal to the current substring of s1 (s1[0]…s1[s1_index - 1]). This is because, in this case, s2 is empty, so all the characters in s3 must come from s1.

• For the first row (s1_index = 0 and s2_index > 0), each cell will be filled with TRUE as long as the prefix of s3 up to that point is equal to the current substring of s2 (s2[0]…s2[s2_index - 1]). This is because, in this case, s1 is empty, so all the characters in s3 must come from s2.

As the base case logic outlined above indicates, each cell in the lookup table, addressed by the tuple (s1_index, s2_index), represents whether there is any way to interleave the initial s1_index characters of s1 with the initial s2_index characters of s2 to form the string represented by the initial s1_index + s2_index characters of s3.

Let’s see what we mean by this with a couple of examples:

1. Given s1 = “uvx”, s2 = “wyz” and s3 = “uvwxyz”, lookup_table[2][1] represents whether there is any way to interleave the initial $2$ characters from s1, “uv”, and the initial character from s2, “w”, to make “uvw”, the initial $2+1=3$ characters in s3. Since this is possible, the result of this subproblem is TRUE.

2. Similarly, lookup_table[2][2] represents whether there is any way to interleave the initial $2$ characters from s1, “uv”, and the initial $2$ characters from s2, “wy”, to make “uvwx”, the initial $2+2=4$ characters in s3. Since this is not possible, the result of this subproblem is FALSE.

Let’s walk through the process of checking whether the given strings, s1 and s2, are interleaved to form s3: